home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group92c.txt / 000024_icon-group-sender _Mon Oct 19 14:17:00 1992.msg < prev    next >
Internet Message Format  |  1993-01-04  |  4KB
  1. Received: by cheltenham.cs.arizona.edu; Mon, 19 Oct 1992 12:35:02 MST
  2. Message-Id: <199210191919.AA25581@optima.cs.arizona.edu>
  3. From: nowlin@iwtqg.att.com
  4. Date: Mon, 19 Oct 92 14:17 CDT
  5. To: att!cs.arizona.edu!icon-group
  6. Subject: Re: sorting on multiple fields
  7. Status: R
  8. Errors-To: icon-group-errors@cs.arizona.edu
  9.  
  10. There must be something like this in the IPL but here's what I've used for
  11. years if I wanted to sort a list of records by various fields.  It could
  12. also be used for lists of lists but the variable names would make that a
  13. little confusing.
  14.  
  15. Jerry Nowlin
  16.  
  17. ----------------------------------> cut here <--------------------------------
  18. # This example program is to illustrate the recsort() procedure.  It sorts
  19. # a UNIX style password file.  The arguments to the program should be the
  20. # fields in each password entry to sort on in order of precedence.  The
  21. # program has a built-in limit of the first 20 entries in the password file
  22. # but it can be removed to test the program on the whole password file.
  23. # Notice that the UID and GID fields are now forced to be numeric.  Sorts
  24. # on these fields will work accordingly.
  25.  
  26. record passwd(name,pass,uid,gid,info,logdir,shell)
  27.  
  28. procedure main(args)
  29.  
  30.     if *args = 0 then stop("I need a numeric record index to sort on")
  31.  
  32.     users := []
  33.  
  34.     in := open("/etc/passwd","r")
  35.  
  36.     every line := !in\20 do line ? {
  37.  
  38.         user := passwd()
  39.         user.name := tab(upto(':')) & move(1)
  40.         user.pass := tab(upto(':')) & move(1)
  41.         user.uid := numeric(tab(upto(':'))) & move(1)
  42.         user.gid := numeric(tab(upto(':'))) & move(1)
  43.         user.info := tab(upto(':')) & move(1)
  44.         user.logdir := tab(upto(':')) & move(1)
  45.         user.shell := tab(0)
  46.         put(users,user)
  47.  
  48.     }
  49.  
  50.     close(in)
  51.  
  52.     write("UNSORTED: ",image(users)," ",image(users[1]))
  53.     every user := !users do write(    user.name,":",
  54.                     user.pass,":",
  55.                     user.uid,":",
  56.                     user.gid,":",)
  57.                     #user.info,":",
  58.                     #user.logdir,":",
  59.                     #user.shell)
  60.  
  61.     stuff := recsort(users,args)
  62.  
  63.     write("\nSORTED: ",image(stuff)," ",image(stuff[1]))
  64.     every user := !stuff do write(    user.name,":",
  65.                     user.pass,":",
  66.                     user.uid,":",
  67.                     user.gid,":",)
  68.                     #user.info,":",
  69.                     #user.logdir,":",
  70.                     #user.shell)
  71. end
  72.  
  73. # Sort the list of records passed in recs by the list of field indexes
  74. # passed in keys.  A field index must be numeric and refer to one of the
  75. # fields in the record type being sorted.  If a numeric field index is
  76. # negative the positive value will be used but the sorting done on that
  77. # field will be in reverse order.  A sorted list of records is returned.
  78.  
  79. procedure recsort(recs,keys)
  80.  
  81.     # Initialize a temporary table.
  82.     tempt := table()
  83.  
  84.     # Get a sorting key.
  85.     key := get(keys)
  86.  
  87.     # If the key is negative sort in reverse order.
  88.     if key < 0 then {
  89.         key := -key
  90.         getpair := pull
  91.     } else     getpair := pop
  92.  
  93.     # Take every record in the recs list and add it to the table.
  94.     every rec := !recs do
  95.  
  96.         # Each index to the table is a different sorting key.  To
  97.         # avoid losing records which have identical sorting keys
  98.         # each value in the table must be a list of the records
  99.         # that are indexed by a given sorting key.
  100.         (/tempt[rec[key]] := [ rec ]) | put(tempt[rec[key]],rec)
  101.  
  102.     # Sort the table by the indexes (sorting keys).
  103.     templ := sort(tempt,1)
  104.  
  105.     # Initialize a new records list.
  106.     newrecs := []
  107.  
  108.     # Take apart the pairs of lists generated by the sort.
  109.     while pair := getpair(templ) do {
  110.  
  111.         # If there is more than one record in this value list and
  112.         # there are additional keys to sort on recursively sort
  113.         # this value list with the remaining keys.
  114.         if *pair[2] > 1 & *keys > 0 then
  115.             pair[2] := recsort(pair[2],copy(keys))
  116.  
  117.         # Add each record from the value list to the temporary list.
  118.         every put(newrecs,!pair[2])
  119.     }
  120.  
  121.     # Return the new sorted list of records.
  122.     return newrecs
  123. end
  124.